/**
 * Copyright (c) [2025] [何屹林]
 *
 * 保留所有权利。
 *
 * 文件名称：DFA_maker.cpp
 * 模块功能说明：
 * 该模块实现DFA结构体中，定义生成DFA的各种函数，并构建DFA状态转移表，在生成DFA的过程中同步NFA中的单词顺序编码。
 *
 * 华南师范大学-计算机学院-网络工程-1班
 * 作者：何屹林-20222132023
 * 完成日期：2025年7月24日
 */
#include "logic.h"

int DFACnt=0;
QHash<QSet<NFA*>,int>DFASETMAP;

QSet<int>DFAEND;
QSet<int>DFANOTEND;

QVector<DFANode*>nodes;

//求NFA结点的ε闭包
QSet<NFA*>epsilonclosure(NFA* source)
{
    QSet<NFA*>closure;
    QStack<NFA*>prepared;//DFS栈
    QMap<int,int>visited;//记录已经访问过的点
    prepared.push(source);//将初始结点压入栈中
    while(prepared.size())
    {
        NFA*cur=prepared.top();
        prepared.pop();
        if(visited[cur->id]) continue;
        closure.insert(cur);
        visited[cur->id]=1;
        //获取当前状态的ε-转换集合
        QSet<int> eClosure = StateTable[cur->id].char2state[EMPTY];
        for(int num:eClosure)
        {
            prepared.push(NFAHash[num]);
        }

    }
    return closure;
}

//求在指定id处收到指定的符号之后转移的ε闭包
//根据某Symbol进行一次移进，并对结果求EPSILON闭包
QSet<NFA*>forward(NFA*source,QChar symbol)
{
    QSet<NFA*>result;
    //获取当前状态的symbol转换集合
    //set<int> otherClosure = StateTable[current].m[ch];
    QSet<int> togo = StateTable[source->id].char2state[symbol];
    for(int num:togo)
    {
        result.insert(NFAHash[num]);
        //然后再加上它的ε闭包
        QSet<NFA*>closurenext=epsilonclosure(NFAHash[num]);
        result.unite(closurenext);

    }
    return result;
}

//在DFA图生成完毕（也就是已经把全部的DFA结点存到vector里面之后），为每一个单词编码
void DFAcode()
{
    for(auto&x:nodes)
    {
        for(auto &y:x->NFANodes)
        {
            if(ExitNFA.contains(NFAHash2[y]))
            {

                if(y->isExit==true)
                {x->cd=ExitNFA[NFAHash2[y]];break;}
                else
                {
                    x->cd=-1;
                }
            }
        }
        if(x->cd>maxcode||x->cd<0)
        {x->cd=-1;}
    }
}

//生成DFA图,实际上是构造好一群DFA结点，通过DFA->transfer联系
//完成这一步之后就把DFA结点都存到了nodes里面
void Logic::DFA_maker()
{
    DFANode*start =new DFANode();
    //将NFA结点列表绑定到DFA状态中
    start->mergeNFA(epsilonclosure(resultNFA.start));

    if(start->flag=="o")
    {
        DFAEND.insert(DFACnt);
    }
    else
    {
        DFANOTEND.insert(DFACnt);
    }
    DFASETMAP[start->NFANodes]=DFACnt++;
    start->flag="i";

    //加入初始结点
    nodes.push_back(start);
    for(int i=0;i<nodes.size();++i)
    {
        DFANode*cur=nodes[i];
        for(QChar symbol:Chars)
        {
            QSet<NFA*>NFANodesOfSymbol;
            for(NFA*next:cur->NFANodes)
            {
                QSet<NFA*>NFANodesOfNext=forward(next,symbol);
                NFANodesOfSymbol.unite(NFANodesOfNext);
            }
            if(NFANodesOfSymbol.isEmpty()) continue;
            //判断是不是新增的结点
            DFANode*instance =new DFANode(nodes.size());
            instance->mergeNFA(NFANodesOfSymbol);
            //子集构造法
            for(DFANode*exist:nodes)
            {
                if(*exist==*instance)
                {
                    instance=exist;
                    break;
                }
            }
            if(instance->id==nodes.size())//需要新增一个DFA结点
            {
                //DFACnt++;
                nodes.push_back(instance);
                if(instance->flag=="o")
                {
                    DFAEND.insert(DFACnt);
                }
                else
                {
                    DFANOTEND.insert(DFACnt);
                }
                DFASETMAP[instance->NFANodes]=DFACnt++;
            }
            //加入转移关系
            cur->transfer[symbol]=instance->id;
        }
    }
    //状态编码
    for(int i=1;i<nodes.size();++i)
    {
        nodes[i]->id=i;
    }

    DFAcode();
}

//生成DFA图


//将QSet<NFA*>NFANodes;//并进来的NFA结点，转成对应的id的集合，便于打表
QSet<int>NFAIDS(QSet<NFA*>NFAnodes)
{
    QSet<int>result;
    for(const auto nn:NFAnodes)
    {
        int idd=NFAHash2[nn];
        result.insert(idd);
    }
    return result;

}

//生成DFA图

void Logic::genDFA()
{
    QVector<QString>headers{"状态","ID","同类NFA状态集合"};
    int colCnt=headers.size();
    QMap<QChar,int>charCol;
    for(const auto&c:Chars)
    {
        if(C2S.contains(c))
        {
            headers.push_back(trim(C2S[c]));
        }
        else
        {
            headers.push_back(c==ANY?"ANY":STR(c));
        }
        charCol[c]=colCnt++;
    }
    int rowCnt=nodes.size()+1;
    DFATable.resize(rowCnt,QVector<QString>(colCnt));
    DFATable[0]=headers;
    int row=1;
    for(const auto&x:nodes)
    {
        DFATable[row][0]=x->flag;//第一列放flag
        DFATable[row][1]=QString::number(x->id);//第二列放ID
        DFATable[row][2]=set2string(NFAIDS(x->NFANodes));//第三列放NFA状态集合的id，NFAIDS将NFA集合转成对应id的集合，set2string函数生成可视化结果

        for(auto entry=x->transfer.begin();entry!=x->transfer.end();++entry)
        {
            DFATable[row][charCol[entry.key()]]=QString::number(entry.value());
        }
        ++row;
    }
    // for(int i=1;i<nodes.size();++i)
    // {
    //     if(nodes[i]->flag=="o")
    //     //qDebug()<<nodes[i]->id<<"号为出口，出口编码为"<<nodes[i]->cd<<"   ";
    // }
    //qDebug()<<DFACnt;
    //qDebug()<<maxcode;
    //qDebug()<<CdPrec[17];
    //qDebug()<<ccdd["else"];
    //qDebug()<<ccdd["ID"];
}

//创建表格显示DFA
void Logic::DFATableShow(const QString& title) {

    QStringList colHeader,header;
    for(int i=1;i<=DFATable.size();i++)
        colHeader.append(QString::number(i));

    for(int i=1;i<=DFATable[0].size();i++)
        header.append(QString::number(i));

    formShow(title,header,colHeader,DFATable);
    return;
}
